package com.lun.medium;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class MinimumCostTreeFromLeafValues {

	// 方法一：我自己写的，DP，从下而上
	public int mctFromLeafValues(int[] arr) {
		int dp[][] = new int[arr.length][arr.length];

		// 初始化元素值
		// 其实这段可省略，合并到下面一段循环。如果要省略，将下面stepWidth初始化为1
		for (int i = 0; i + 1 < arr.length; i++) {
			dp[i][i + 1] = arr[i] * arr[i + 1];
		}

		for (int stepWidth = 2; stepWidth < arr.length; stepWidth++) {
			for (int i = 0; i + stepWidth < arr.length; i++) {
				int min = Integer.MAX_VALUE, end = i + stepWidth;
				for (int j = i; j < end; j++) {// j 将数组分成两段
					int temp = dp[i][j] + max(arr, i, j) * max(arr, j + 1, end) //
							+ dp[j + 1][end];
					if (temp < min)
						min = temp;
				}
				dp[i][end] = min;
			}
		}

		return dp[0][arr.length - 1];
	}

	private int max(int[] array, int start, int end) {
		int max = array[start];
		for (int i = start + 1; i <= end; i++)
			if (array[i] > max)
				max = array[i];
		return max;
	}

	// 方法一之二：别人写的，DP，从上而下
	public int mctFromLeafValues2(int[] arr) {
		int n = arr.length;
		int[][] dp = new int[n][n];
		return dfs(arr, 0, n - 1, dp);
	}

	public int dfs(int[] arr, int s, int e, int[][] dp) {
		if (s == e)
			return 0;
		if (dp[s][e] > 0)
			return dp[s][e];
		int ans = Integer.MAX_VALUE;
		for (int i = s; i < e; i++) {
			int left = dfs(arr, s, i, dp);
			int right = dfs(arr, i + 1, e, dp);
			int maxLeft = 0, maxRight = 0;
			for (int j = s; j <= i; j++)
				maxLeft = Math.max(maxLeft, arr[j]);
			for (int j = i + 1; j <= e; j++)
				maxRight = Math.max(maxRight, arr[j]);
			ans = Math.min(ans, left + right + maxLeft * maxRight);
		}
		dp[s][e] = ans;
		return ans;
	}

	// 方法二：贪心算法
	public int mctFromLeafValues3(int arr[]) {
		List<Integer> A = new ArrayList<>();
		for (int d : arr)
			A.add(d);

		int res = 0;
		while (A.size() != 1) {
			int minIndex = A.indexOf(Collections.min(A));

			if (minIndex > 0 && minIndex < A.size() - 1)
				res += A.get(minIndex) * Math.min(A.get(minIndex - 1), A.get(minIndex + 1));

			else if (minIndex == 0)
				res += A.get(minIndex) * A.get(minIndex + 1);
			else
				res += A.get(minIndex) * A.get(minIndex - 1);

			A.remove(minIndex);
		}
		return res;
	}

	// 方法三：单调栈
	public int mctFromLeafValues4(int[] arr) {
		if (arr == null || arr.length < 2) {
			return 0;
		}

		int res = 0;
		LinkedList<Integer> stack = new LinkedList<>();
		for (int num : arr) {

			// while num is bigger than peek(), pop and calculate
			while (!stack.isEmpty() && stack.peek() <= num) {
				int mid = stack.pop();
				if (stack.isEmpty())
					res += mid * num;
				else
					res += mid * Math.min(stack.peek(), num);
			}

			stack.push(num); // if num is smaller, push into stack
		}

		// if there are values left in the stack, they sure will be mutiplied anyway
		// and added to the result.
		while (stack.size() > 1) { // > 1 because we have a peek() after pop() below
			res += stack.pop() * stack.peek();
		}

		return res;
	}

}
